package Lee_code;

public class Lee_1049 {
    public int lastStoneWeightII(int[] stones)
    {
        int len = stones.length;
        int sum = 0;
        for(int stone: stones)
        {
            sum = sum+stone;
        }
        int target = sum/2;
        int[] dp = new int[target+1];
        //i是物品, j是背包容量
        for(int i=0; i<stones.length; i++)
        {
            for(int j=target; j>=stones[i] ;j--)
            {
                dp[j] = Math.max(dp[j], dp[j-stones[i]] + stones[i]);
            }
        }
        return sum - dp[target]*2;
    }
}
